#include "main/utils.h"
using namespace std;

int reverseString(const string& s) {
  int length = s.size();
  if (length == 0)
    return 0;

  vector<int> f, g;
  f.push_back(s[0] == '0' ? 0 : 1);
  g.push_back(s[0] == '0' ? 1 : 0);
  for (int i = 1; i < length; ++i) {
    f.push_back(s[i] == '0' ? f[i - 1] : f[i - 1] + 1);
    g.push_back(s[i] == '0' ? min(f[i - 1], g[i - 1]) + 1 : min(f[i - 1], g[i - 1]));
  }
  return min(f.back(), g.back());
}

int reverseString1(const string& s) {
  int length = s.size();
  if (length == 0)
    return 0;

  int f[2], g[2];
  f[0] = (s[0] == '0' ? 0 : 1);
  g[0] = (s[0] == '0' ? 1 : 0);
  for (int i = 1; i < length; ++i) {
    f[i % 2] = (s[i] == '0' ? f[(i - 1) % 2] : f[(i - 1) % 2] + 1);
    g[i % 2] = (s[i] == '0' ? min(f[(i - 1) % 2], g[(i - 1) % 2]) + 1 : min(f[(i - 1) % 2], g[(i - 1) % 2]));
  }
  return min(f[(length - 1) % 2], g[(length - 1) % 2]);
}

int main() {
  string s = "00110";
  cout << reverseString(s) << endl;
  cout << reverseString1(s) << endl;

  return 0;
}
